\documentclass{vldb}
\usepackage{times,amsmath,epsfig}
 \usepackage{qtree}

\usepackage{listings,lipsum}

%
\usepackage{makeidx}  % allows for indexgeneration
%
\usepackage{balance} 
\usepackage{xcolor}
\usepackage{tikz}
\usepackage{pgfplots}

\usepackage{graphicx}
\usepackage{stfloats}
\usepackage{amsmath}
\usepackage{bbm}
\usepackage{amssymb}
\usepackage{multirow}
\usepackage{mathrsfs}
\usepackage{url}
\usepackage{listings}
\usepackage{color}
\usepackage{wrapfig}
\usepackage{mathtools}
 
\usepackage{algorithm}
\usepackage{algorithmic} 

\lstloadlanguages{XML}

\renewcommand{\baselinestretch}{0.96}
\newcommand{\beq}{\begin{equation}}
\newcommand{\enq}{\end{equation}}
\newcounter{mytempeqncnt}
\newcommand{\bquote}{\begin{quote}}
\newcommand{\equote}{\end{quote}}
\newtheorem{lemma}{Lemma}
\newcommand{\todo}[1]{\textcolor{red}{@TODO: #1}}
\newcommand{\dtr}[1]{\textbf{\textit{#1}$^\textbf{[dtr]}$}}
\algsetup{linenosize=\small}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}
\sloppy 
\lstnewenvironment{listingh}[1][]{%
    \lstset{#1}%
}{%
    \vspace{-\baselineskip}%
}

\DeclareTextCommandDefault{\textvisiblespace}{%
  \mbox{\kern.06em\vrule \@height.3ex}%
  \vbox{\hrule \@width.3em}%
  \hbox{\vrule \@height.3ex}}
  
 
  
\begin{document}
\title{Learning Edit-Distance Based String Transformation Rules From  Examples}
%
 
\numberofauthors{2} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.
%
\author{
\alignauthor Samur Araujo \\
       \affaddr{Delft University of Technology, }\\
       \affaddr{PO Box 5031, 2600 GA }\\
       \affaddr{Delft, the Netherlands}\\
       \email{s.f.cardosodearaujo@tudelft.nl}
\alignauthor Arjen de Vries \\
       \affaddr{Delft University of Technology, }\\
       \affaddr{PO Box 5031, 2600 GA }\\
       \affaddr{Delft, the Netherlands}\\
       \email{a.p.devries@tudelft.nl}
}
 

\maketitle
\begin{abstract}
The task of transforming a string from a source format into a target format is encountered in many  information-processing tasks. Consider the task of  transforming a list of names in the form \textit{``firstname lastname"} (e.g.\  ``Michael Jackson") into the target form \textit{``lastname first letter of the firstname"} (e.g.\ ``Jackson M").  In many domains, identifying an appropriate set of operations that transforms one string to another is challenging, as the space of possible transformations is large. In this paper, we investigate the problem of learning string transformation rules from pairs of example strings. We propose a solid way to design these rules based on only four string operations: permutations, insertions, deletions and updates. Additionally, we propose an efficient algorithm to learn such   rules, implemented as a combination of variations of well-known string manipulation algorithms. The proposed algorithm has the following desirable properties: it can express any string transformation; it can produce transformation rules that correctly transform a large part of the data, even when a limited number of training examples is provided; it is linear w.r.t the training sample size, which allows it to scale for large tasks; and it easy to understand and implement. We demonstrate the ability of our algorithm over real-world transformation tasks. The results indicate that the algorithm learns transformation rules that are generalizable for a broader range of strings to be transformed, using very few examples. The algorithm is especially useful for spreadsheets and data cleaning tool  developers that want to support their end-users on string transformation related tasks.
\end{abstract}
 
%% A category with the (minimum) three required fields
%\category{H.3.3}{Information Storage and Retrieval}{ Information Search and Retrieval-Search process, Selection process, Information filtering;}
%
%\terms{Algorithms, Experimentation}
%
%\keywords{query optimization, instance matching, remote querying, data integration, linked data} % NOT required for Proceedings
%\input{content}
\bibliographystyle{abbrv}
\bibliography{paper}  % sigproc.bib is the name of the Bibliography in this case

\end{document} 